package hot_100;

import java.util.*;

/**
 * @author: Darven
 * @createTime: 2025-09-21  22:12
 * @description: TODO
 */
public class P239 {

    Deque<Integer> queue = new ArrayDeque<>();

    public static void main(String[] args) {
        P239 p239 = new P239();
        int[] ints = p239.maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3);
        for (int i:ints){
            System.out.println(i);
        }
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] ans=new int[nums.length-k+1];
        int index=0;
        for (int i=0;i<nums.length;i++){
           if(i<k-1){
               push(nums[i]);
           }
           else{
               push(nums[i]);
               ans[index++]=getMax();
               // 如果窗口左边的数是最大的就直接去掉，因为会留到下一个窗口
               poo(nums[i-k+1]);
           }
        }
        return ans;
    }

    /**
     * 如果比队尾大，就将队尾去掉，保证单调性
     * */
    public void push(int value) {
        while (!queue.isEmpty() && queue.peekLast() < value) {
            queue.pollLast();
        }
        queue.offerLast(value);
    }

    /**
     * 单调递减，所以出队头
     * */
    public int getMax(){
        if (queue.isEmpty()){
            throw new RuntimeException("队列为空");
        }
        return queue.peekFirst();
    }

    /**
     * 去除对应值,只有队头的时候
     * */
    public void poo(int value){
        if(!queue.isEmpty()&&queue.peekFirst()==value){
            queue.pollFirst();
        }
    }
}


